package leetcode_core.leetcode_6;


import java.util.Arrays;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年02月08日 20:52
 */
public class Heap {
    private final int[] nums;
    private int heapSize;
    public Heap(int n){//预定堆顶的大小
        nums = new int[n];
        heapSize = 0;
    }

    public Heap(int[] nums){//预定堆顶的大小
        this.nums = nums;
        heapSize = 0;
        //buildHeap
        for (int num : nums) {
            push(num);
        }
    }

    public int[] getHeap(){
        return nums;
    }


    /**
     * 执行堆的插入,heapSize的位置,与父亲比较,如果比父亲大,就把父亲PK下来
     * @param num
     */
    public void push(int num){
        int index = heapSize;
        nums[heapSize++] = num;
        int parent = (index-1)/2;
        while(nums[index] > nums[parent]){
            //然后交换两个位置上的数字
            nums[index] = nums[index]^nums[parent];
            nums[parent] = nums[index]^nums[parent];
            nums[index] = nums[index]^nums[parent];
            //然后子节点指针去指向父亲节点
            index = parent;
            parent = (index-1)/2;
        }
    }

    public int pop(){
        //就是将第一个数字和最后一个数组交换
        heapSize--;
        if(heapSize == 0){
            return nums[0];
        }
        nums[0] = nums[0]^nums[heapSize];
        nums[heapSize] = nums[heapSize]^nums[0];
        nums[0] = nums[heapSize]^nums[0];
        int max = nums[heapSize];
        //然后要做堆的调整
        //初始化,根0左孩子1
        int left = 1;
        int index = 0;
        while(left < heapSize){//当还有孩子的时候
            //判断左右孩子和父亲节点的大小关系
            int bigger = left;
            int right = left+1;
            //1.1 如果右孩子存在 && 右孩子比左孩子要大
            if(right < heapSize && nums[right] > nums[left]){
                bigger = right;
            }
            //1.2 如果父亲把左右孩子都PK掉了,那么就直接break
            if(nums[index] >= nums[bigger]){
                break;
            }
            //否则的话就是子节点更大,然后我们执行交换
            nums[index] = nums[index]^nums[bigger];
            nums[bigger] = nums[index]^nums[bigger];
            nums[index] = nums[index]^nums[bigger];
            //注意,由于这时候父节点被换到子节点去了,但是它能不能镇住子节点呢?不确定,因此必须再迭代
            index = bigger;
            left = (index *2)+1;
        }
        return max;
    }

    public static int[] heapSort(int[] nums){
        //1.buildHeap
        Heap heap = new Heap(nums);
        int n = nums.length;
        while (n-->0){
            int pop = heap.pop();
            System.out.println(pop);
        }
        return nums;
    }


    public static void main(String[] args) {
        int[] nums = new int[]{6,5,4,3,2,1};
        System.out.println(Arrays.toString(heapSort(nums)));
    }
}
